Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Oracle Hard
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Max Points on a Line

Problem Statement

Given an array containing points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that are on the same straight line.

Examples

  • Example 1:

    • Input: points = [[1,2], [3,6], [5,10], [7,14]]
    • Expected Output: 4
    • Justification: All points lie on the line (y = 2x), forming a straight line with all given points.
  • Example 2:

    • Input: points = [[1,1], [2,2], [3,3], [8,10]]
    • Expected Output: 3
    • Justification: The first three points form a line with the equation (y = x), while the fourth point does not lie on this line.
  • Example 3:

    • Input: points = [[0,0],[-3,0], [1,1], [2,2], [3, 0], [6, 0]]
    • Expected Output: 4
    • Justification: Points ([1,1]), ([2,2]), and ([0,0]) lie on the line (y = x), making a straight line. The point ([0,0]), (-3, 0), (3, 0), and (6, 0) lie on the x-axis. So, the maximum points on the straight line is 4.

Solution

To solve this problem, we'll leverage the concept of calculating the slope between any two points to determine if they lie on the same line. By iterating over each point and comparing it with every other point, we can calculate the slope and use a hash map to track the number of points that share the same slope with respect to a given point.

This approach ensures we consider every possible line that can be formed with the given points. The key to solving this efficiently lies in accurately calculating and comparing the slopes, taking care of potential issues like vertical lines (where the slope is infinite) and floating-point precision errors. We believe this method is effective because it systematically examines all pairs of points to identify the maximum subset that aligns linearly, thereby ensuring no possible line is overlooked.

Step-by-Step Algorithm

  1. Define a Helper Function for GCD: Implement a recursive method gcd to find the greatest common divisor of two numbers. This is crucial for simplifying the slope to its most reduced form, ensuring that slopes are consistently calculated across different pairs of points.

  2. Define the Main Function maxPoints:

    • Check if the input points list has fewer than 3 points. If so, return its length, as any two points or a single point always lie on a straight line by definition.
  3. Initialize the Maximum Count Variable: Create a variable max_count to keep track of the maximum number of points found on a single line throughout the iteration.

  4. Iterate Over Each Point: Use a loop to iterate through each point in the points list. This point will act as a reference point for calculating slopes to every other point.

  5. Handle Duplicates and Initialize Local Maximum: For each reference point, initialize duplicate to 1 (to count the reference point itself) and local_max to 0. These variables track the number of duplicate points and the maximum number of points on a line with the same slope, respectively.

  6. Create a Slope Map: Initialize a slope_map hashmap to store the count of points that form the same slope with the reference point.

  7. Iterate Over Other Points to Calculate Slopes:

    • For each other point, calculate the differences delta_x and delta_y.
    • If both delta_x and delta_y are 0, it means the point is a duplicate of the reference point. Increment duplicate and continue.
    • Calculate the greatest common divisor (GCD) of delta_x and delta_y, and reduce them by this GCD to get the simplest form of the slope.
    • Convert the slope to a string format "{delta_y}/{delta_x}" and use it as a key in slope_map to count how many points share this slope.
  8. Update Local and Global Maximums: After checking all points against the current reference point, update local_max to reflect the highest number of points on a line for the current slope. Then, update max_count with the greater of its current value or local_max + duplicate.

  9. Return the Maximum Count: After iterating through all points, return max_count as the solution.

Algorithm Walkthrough

Let's consider the Input: points = [[0,0],[-3,0], [1,1], [2,2], [3, 0], [6, 0]].

  • Initialization: max_count is set to 0.

  • First Iteration (Reference Point [0,0]):

    • duplicate is 1. slope_map is empty: {}.
    • Compare with [-3,0]: delta_x = -3, delta_y = 0,Gcd(-3, 0) = -3, slope is "(0/-3)/(-3/-3)". slope_map becomes {"0/1": 1}.
    • Compare with [1,1]: delta_x = 1, delta_y = 1, slope is "1/1". slope_map becomes {"0/2": 1, "1/1": 1}.
    • Compare with [2,2]: delta_x = 2, delta_y = 2, slope is "1/1" (after reduction). slope_map updates to {"0/-3": 1, "1/1": 2}.
    • Compare with [3,0]: delta_x = 3, delta_y = 0,Gcd(3, 0) = -3, slope is "(0/3)/(3/3)". so slope_map updates to {"0/1": 2, "1/1": 2}.
    • Compare with [6,0]: delta_x = 6, delta_y = 0,Gcd(6, 0) = 6, slope is "(0/6)/(6/6)". so slope_map becomes {"0/1": 3, "1/1": 2}.
    • local_max is 3 for the slope "0/-3", adding duplicate (1), max_count becomes 4.
  • Second Iteration (Reference Point [-3,0]):

    • Initialization: For this iteration, duplicate is again set to 1, and slope_map is reset to empty: {}.

    • Compare with [1,1]:

      • delta_x = 4 (1 - (-3)), delta_y = 1 (1 - 0).
      • gcd(4, 1) = 1, so the slope remains "1/4".
      • Update slope_map to {"1/4": 1}.
    • Compare with [2,2]:

      • delta_x = 5, delta_y = 2.
      • gcd(5, 2) = 1, slope simplifies to "2/5".
      • Update slope_map to {"1/4": 1, "2/5": 1}.
    • Compare with [3,0]:

      • delta_x = 6, delta_y = 0.
      • gcd(6, 0) = 6, resulting in the simplified slope "0/1".
      • Update slope_map to {"0/1": 1, "1/4": 1, "2/5": 1}.
    • Compare with [6,0]:

      • delta_x = 9, delta_y = 0.
      • gcd(9, 0) = 9, slope simplifies to "0/1".
      • Update slope_map to {"0/1": 2, "1/4": 1, "2/5": 1}.
  • Determine local_max for this iteration:

    • The highest count in slope_map is for the slope "0/1", which is 2. Since duplicate is 1, and considering this iteration does not add any new points to the line (duplicates were handled in the first iteration), local_max is 2.
  • Update max_count:

    • The global max_count remains 4 from the first iteration, as local_max + duplicate (2 + 1) does not exceed the current max_count.
  • Subsequent Iterations: Repeat the process for each point as the reference point. However, the first iteration already found the maximum count of 4, which matches the maximum possible for any line in this set of points.

  • Conclusion: The function returns max_count = 4, which is the maximum number of points on a straight line in the given list of points.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The time complexity of the solution is . This arises because for each point, we compare it to every other point, leading to an complexity. Within this nested loop, we calculate the Greatest Common Divisor (GCD) for the slope, which can be done in time using the Euclidean algorithm, where (n) is the maximum value of the coordinates. Thus, the total time complexity becomes .

Space Complexity

The space complexity is . The primary extra space usage comes from the hash map used to store the slopes and their counts for each point considered as a starting point. In the worst case, the hash map could have an entry for every other point in the dataset if no two points form a line with the same slope, thus leading to space usage.

Max Points on a Line (hard)
Sudoku Solver (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity